One of the challenges in the field of cryptography is to encrypt data in a way that is hard to decrypt for someone who does not have secret information, commonly called a key. One class of techniques for encryption involves using what are called “hyperelliptic curves,” which are curves defined using advanced, abstract mathematics. This kind of encryption and decryption uses keys that are generated using characteristics of a hyperelliptic curve.
A hyperelliptic curve can be defined by a group of points which are mathematically related. In practice, the derivative (called a “Jacobian”) of the hyperelliptic curve is used to specify the curve, and the points on this Jacobian are the group of points. A point P in this group is multiplied by a key N, which is the secret information. While the point P is known, and the product of N and P is known, N is difficult to determine from this information. The simplest type of hyperelliptic curve is called an elliptical curve, which are also called “genus 1” curves. A more complex hyperelliptic curve is called a “genus 2” curve.
To create a genus 2 curve useful for cryptography, three auxiliary polynomials with rational coefficients are computed. From these, the genus 2 curve is computed. These auxiliary polynomials are called Igusa class polynomials. Computation of Igusa class polynomials is very difficult and computationally expensive, and typically is done through an exhaustive search of possible solutions given some starting values.